The Internet Protocol (IP) works by sending packets across multiple networks from a source machine (or “host”) to a destination machine (also known as a “host”). When crossing from one network to another, these packets are processed by gateways, which may reformat the packet in limited ways for transmission across the following network.
IP has a mechanism which allows a gateway to fragment IP packets into smaller pieces (known as “fragments”) if this is required by the next network that the packet will transit. Fragmented packets are reassembled at their destination.
Security gateways are gateways that implement the IPsec protocol to ensure authenticity and/or confidentiality of packets that cross them. In security parlance, a security gateway has a “red” side and a “black” side. Data on the red side are private and need protection. Data on the black side are at least authenticated and hence are protected from modification by unauthorized parties. Data on the black side may additionally be encrypted, and may thus be protected from being read by unauthorized parties. A host may also implement the IPsec protocol; such a node will be called an “IPsec host” for purposes of this written description. Similarly, “IPsec node” will be used to designate either a security gateway or an IPsec host.
Security gateways use IPsec by wrapping packets received on the red side in an IPsec packet which is then carried inside an IP packet transmitted on the black side. Where a security gateway receives a packet that was fragmented while transiting the black network, the security gateway needs to reassemble the packet before the packet can be authenticated. This poses the risk of a potential denial-of-service (DOS) attack on a security gateway. Namely, a malicious user may flood the receiving security gateway with a large number of spurious packages that render reassembly at the receiving security gateway time-consuming and costly. Additionally, the receiving security gateway may be fooled into assembling spurious fragments with real fragments. Such incorrectly assembled packets may eventually be discarded because of their failure to be authenticated at the receiving security gateway; however, the attack will have succeeded because of the resources wasted in connection with assembling the packet containing spurious fragments.
Path MTU Discovery
Because fragmentation and reassembly impose costs on communication, the Internet community has created protocols and standards for discovering the maximum transmission unit (MTU) size for the path between two hosts. These protocols are known as PMTU (for Path MTU) discovery protocols.
PMTU discovery, when possible, provides a reliable hint for what MTU to use to send maximal-sized packets that avoid fragmentation on the way to the destination. Such information can only be considered a “hint” however, because changes in the network may change the routing path of packets sent from the source to the destination, which in turn may result in a different MTU for the new path.
PMTU discovery is typically implemented by sending IP datagrams (i.e., packets) of increasing size from the source to the destination in which the “Don't Fragment” (DF) bit in the fragmentation flag field of the IP header for each datagram is set to the value logical “1”. When the size of a packet exceeds the maximum packet size value of one of the networks on the path, the gateway at the boundary of the network will discard the packet and send an Internet Control Message Protocol (ICMP) message back to the source. The PMTU is the length of the largest message that is shorter than the shortest message that triggers such an ICMP message. In this manner, the source may discover the PMTU for packets sent along the current path from the source to the destination. Additionally, the source may repeat the PMTU discovery process periodically to determine whether the path of transmitted packets to the destination has changed due to network traffic conditions.
PMTU discovery is not universally implemented, and there are some system administrators that do not permit ICMP “your message was too large”-messages to leave their networks out of fear that such messages represent a security vulnerability.
If one can discover the PMTU, then fragmentation can be performed on the red side of a security gateway. This will mean that all fragments are authenticated using IPsec, which removes fragment reassembly as a potential DOS vulnerability at the receiving security gateway. However, such PMTU information may not be available, whatever the reason.
16 Bits of IP-ID are not Enough
Reassembling fragments requires that a receiving IPsec node keep the fragments received in queue for a finite amount of time and wait for all the fragments to arrive. An attacker can interfere with a communication stream by causing a reassembler to insert a forged fragment into the queue, which will prevent received packets from being reassembled correctly.
As is known in the art, in Internet Protocol, each fragment of a parent packet contains a full IP header with most information in the fields of the IP header of the fragment inherited from the parent packet. In particular, each fragment will contain the same source host address information in the IP source address field, the same destination host information in the IP destination address field, and the same identification information in the 16-bit IP identification field as the parent packet. The first fragment of a packet will additionally contain header information from the higher-level protocols carried in the packet. As a result of fragmentation, fragments may overlap, duplicate fragments may arrive, and fragments may arrive out-of-order; however, most of these occurrences are rare in current networks, and the receiving node may in most cases ignore out-of-order, overlapping, or duplicate fragments.
Since a receiving security gateway (or more generally, an IPsec node) cannot tell if a fragment is valid until the corresponding packet has been reassembled and authenticated using IPsec, an attacker can force the receiving security gateway (or the IPsec node) to either assemble a packet containing forged elements, in which case the IPsec authentication will fail and the attack will have succeeded, or spend resources making multiple reassembly attempts based on differing combinations of arriving fragments. As the authentication process is expensive in terms of computer time, multiple reassembly attempts are a strain on the resources of the receiving security gateway or IPsec node. If the attacker could insert two false fragments, the attacker would quadruple the difficulty or processing time of the task of reassembly and verification. If the fragmentation behavior along the path to the receiving security gateway or IPsec node is predictable (for example, fragmentation behavior is such that all fragments but the last one are N bytes long), then even approaches that give preference to fragments that better fit with others and that do not overlap are vulnerable to this type of attack. Therefore, a malicious person could clog the reassembly machinery with a minimal amount of work.
The amount of time that a fragment waits in the reassembly queue is determined by how much time separates arriving fragments at the reassembling node. This, in turn, is influenced by factors in the network, such as the speed of intermediate links and queuing delays in intermediate routers.
One can set a minimum lower bound on how long the reassembly queue for a given packet must survive based on the minimum-speed link between the two ends of a IPsec protocol security association and the size of the fragments transmitted across that link. Two 256 Byte (i.e., 211 bit) fragments arriving simultaneously at the upstream end of a 10 Megabit per second (i.e., 223 bit/s) link—e.g., a wireless Ethernet—will be separated by 0.2 milliseconds (2−12 seconds or about 0.2×10−3 seconds) at the downstream end of the 10 Mbps link. This separation arises from the amount of time it takes for the second fragment to traverse the link. Larger fragment sizes only exacerbate the problem.
The minimum MTU allowed by version six of IP, IPv6, can be taken as a hint as to the capabilities that will be built into future networks. The MTU in IPv6 is 1280 Bytes (1280 B). Additionally, recent discussions regarding the non-support of PMTU in the public Internet cites the 1400 B packets on Sun Microsystem Inc.'s PPP-over-Ethernet as being a problem. Therefore, it seems reasonable to expect fragments of size 1024 B or more. 1024 B fragments would take 800 μsec to squeeze through a 10 Mbps link.
The example discussed above concerned the reassembly of two-fragment packets—more fragments per packet will also increase the probable lifetime of a reassembly queue. Unpredictable network queuing delays would also add to the expected lifetime of a fragment on a reassembly queue.
However, in this discussion of fragment size, one should remember that fragmentation may possibly occur such that a slightly-too-large packet will get fragmented into a large packet followed by a small one—e.g., the first fragment may be 1024 B, while the second one is only 100 B In this case, the reassembly-queue lifetime would be shorter than otherwise expected, because it would be dictated by the size of the second and subsequent packets, not the size of the first.
Are these time-scales long enough to present a vulnerability to DOS attacks?
Assume that an attacker wants to interfere with reassembly of packets between a specific pair of hosts, A and B. How much time would it take for an attacker to send 216 fragments, each corresponding to one of the 216 combinations possible in the IP identification field of an IP header for packets in flight between A and B? Such fragments need not be large for an effective attack—21-28 B may be sufficient (the smaller size corresponds to one byte of data with the relevant bit of the fragmentation flag set to a value indicating a final fragment, while the larger size is the smallest possible IP fragment that is not a final fragment)—though such unusually small fragments might be discarded as part of a strategy for dealing with DOS attacks. One may assume that the attacker uses a range of sizes averaging 128 B (210 bits).
For a link with a bandwidth of 100 Gbps, it takes only 10.3 nanoseconds to transmit a single 128 B fragment, and only 670 μs to transmit 216 of them—one for each possible combination in the IP identification field. If the attacker is using only 10% of the link bandwidth, it would take 6.7 ms to transmit a set of fragments corresponding to all possible combination in the IP identification field.
In the 800 μs minimum lifetime of a reassembly queue located at the end of a sub-network with a bandwidth of 10 Mbps (e.g., the wireless Ethernet network discussed earlier), an attacker using 10% of the final link bandwidth can thus cover more than 10% of the IP identification field combinations, and will presumably be able to affect a corresponding portion of our fragments. While this number seems small, it is large enough to mostly shut down a TCP connection. By sending 64 thousand (216) fragments (one for each possible combination in the IP identification field), an attacker can guarantee a collision if fragments get separated in the network by more than 7 milliseconds.
This argument applies even if one imposes the restriction of only accepting fragments in order—all the attacker need do is repeatedly transmit forged second fragments.
In order to support fragment reassembly on a 100 Gbps security gateway, one needs to either be able to ignore or reject forged fragments.
Information in the IPsec header is not present in any fragment other than the initial fragment; such information may even not be present in the initial fragment if the initial fragment is too small to contain such information. Thus, IPsec header information cannot be used to address the discussed DOS attack.
There is thus a need for methods and apparatuses for reducing the probability of denial-of-service attacks based at a security gateway or IPsec node. Such methods and apparatuses need to be able to deal effectively with such attacks where they are based on the fragmentation-related sub-protocols associated with IP.